This invention relates generally to database systems, and more particularly to data replication among multiple servers of a database network.
A database system often contains multiple servers connected via a network. In order to keep the data maintained by each server up to date, changes made by one server are replicated to all other servers of the database system. Replication is the process by which changes present on a xe2x80x9csourcexe2x80x9d server are received by and applied to a xe2x80x9cdestinationxe2x80x9d server. The changes being replicated may have originated on the source server or on another server.
For instance, in a proposed computer network, a plurality of directory service agents (DSAs) each maintain a local database of directory service information. Each of the DSAs can make changes to the directory information, and the changes are replicated to other DSAs in the network. To keep track of the changes to allow proper replication, each change (e.g., creating a new user, changing a user""s password, etc.) originated by a DSA is identified by a database globally unique identification (GUID) and an update sequence number (USN). The database GUID identifies the local database of the DSA in which the change was originated. Each database GUID corresponds to exactly one DSA. The USN is a monotonically increasing serial number that is, for example, a 64 bit number. It increases by one for each originating or replicated-in change applied to the database.
The database GUID and the USN together form a xe2x80x9csignaturexe2x80x9d represented as a (Database-GUID, USN) pair, which uniquely identifies the changexe2x80x94i.e., no two changes should carry the same signature. In this regard, a USN is meaningless without the context of the database GUID for the purpose of uniquely identifying the change. For example, the change (Database-GUID1, 5) does not have any relevance to the change (Database-GUID2, 5). The change (Database-GUID1, 10), on the other hand, does have a relationship to the change (Database-GUID1, 5) in that the change at USN 10 was made after the change at USN 5, because the USNs were associated with the same database GUID and USNs increase over time.
Each update in a DSA""s database is labeled with the signature of the change generated by the originating write and the USN at which the change was applied locally by the DSA. The latter is known as xe2x80x9cusnChanged.xe2x80x9d For an update that originated on the local DSA, the USN in the signature and the usnChanged are identical, and the database GUID in the signature is the database GUID of the local DSA. For an update that originated on another DSA and was later replicated to the local DSA, the USN in the signature (which is relative to the database GUID of the originating DSA) bears no relationship with the usnChanged (which is relative to the database GUID of the local DSA), and the database GUID in the signature is not the database GUID of the local DSA.
To facilitate replication of changes, each DSA tracks xe2x80x9cwatermarksxe2x80x9d of the signatures issued on all other DSAs for changes that it has applied locally. The watermark is an assertion that every change made on the DSA corresponding to the database GUID at or below the given USN has been applied to the local DSA. This includes changes originated on the DSA with the given GUID as well as changes originated on other DSAs that have been applied to the DSA with the given GUID. For example, if DSA2 has recorded the watermark (Database-GUID1, 10), then it asserts that it has applied all changes made in Database-GUID1 at USNs 1, 2, 3, . . . , 10. The set of watermarks a particular DSA has with respect to all other DSAs is known as its xe2x80x9cup-to-dateness vector,xe2x80x9d or xe2x80x9cUTD vector.xe2x80x9d
In this proposed network database, the receiver of changes initiates the replication. In other words, the destination DSA asks the xe2x80x9csourcexe2x80x9d DSA for any changes the source DSA may have that the destination does not. This form of replication is also known as xe2x80x9cpullxe2x80x9d replication. To respond to the replication request, the source DSA needs an efficient method to locate these changes that should be replicated to the destination DSA. It does so by checking in the UTD vector presented by the destination DSA in its request for a watermark relative to the source DSA""s database GUID. If such a watermark is found, and assuming the watermark is X, the source DSA knows that it only has to look at updates in its database with usnChanged value greater than X. This is because the UTD vector indicates that all changes originated or replicated by the source DSA with USN at or below X have already been applied to the destination DSA, so that updates with usnChanged that are less than or equal to X do not have to be replicated again. If no watermark relative to the source DSA""s database GUID can be found, the destination has to look at all updates in its database, i.e., starting at USN 0.
For each update on the source DSA found by comparing its usnChanged with the watermark, the source DSA looks at the signature of the update and references it against the UTD vector provided by the destination. If a watermark is found with the database GUID of the signature of the change, the change has to be sent to the destination DSA if and only if the USN of the signature is greater than the USN in the watermark. This is again because the watermark indicates that the destination has applied all updates at or prior to its associated USN. If no watermark is found with the database GUID of the signature, the update is sent to the destination DSA.
After the destination has received and applied all changes sent by the source DSA, the destination DSA then asserts it is at least as up-to-date with respect to other DSAs as the source DSA is. The destination DSA then updates each of its watermarks to at least the corresponding USN recorded in the watermarks with corresponding database GUIDs at the source, and adds any watermarks relative to database GUIDs not in its own UTD vector but present in the source DSA""s UTD vector.
Although this scheme of controlling data replication based on watermarks can potentially provide efficient data replication across a database system, the reliability of the replication is put in question in the event a server has to be restored from backup. In real-world operations, there is always the risk that the local database of a server will be damaged or somehow made irrecoverable such that the database has to be reconstructed from a backup. A consequence of the restoration is that the restored server has lost the changes it made after the backup and before the restoration. Those xe2x80x9clostxe2x80x9d changes, however, may have already been replicated to other servers in the system. When the restored server continues from the restored state and adds new changes, some of the changes may be given signatures that have already been used for changes made before the restoration and replicated to other servers. Thus, two coexisting yet different changes may have the same signature. This can cause great confusion and inconsistency in the data replication, and, as a result, there is no guarantee of the convergence of the data on different servers through replication. Different approaches, such as the xe2x80x9cbacksyncingxe2x80x9d process that will be described in greater detail below, have been proposed to address this problem of replication after restoration, but fail to provide satisfactory results.
There is another scenario in which directory service information may be lost, potentially creating replication inconsistencies. This problem arises in the context of the replication of directory service partition(s) that can be dynamically added to and removed from DSAs. Due to the removal and/or addition of one or more partitions, current replication techniques, as applied to DSAs, may lose some changes, causing inconsistency across DSAs. Consequently, it would be desirable to provide a solution wherein information that is replicated in a distributed system may persist across the addition and removal of partitions, thereby preventing the loss of directory service information due to the removal/addition of directory service partitions and maintaining consistency across DSAs.
In view of the foregoing, the present invention provides a method and system for replicating database changes among servers of a database system that effectively removes the inconsistency problems encountered after restoration from backup and due to removal and re-addition of partitions by assigning a new GUID to a server after it has been restored or after the partition has been re-added. This new GUID is used for identifying new changes made by the server after restoration or partition re-addition. By virtue of the use of the new GUID, new changes made after restoration will not be confused with any changes made by the server after the backup and before the restoration, which are identified by the old GUID of the server, thereby ensuring convergence of the servers"" data through replication. Similarly, by virtue of the use of the new GUID, new changes made after re-addition of a partition will not be confused with any changes made prior to the removal of the partition.
In the restoration case, the replication performance is further optimized by recording the GUID used by a server and its highest replication sequence number each time a backup of the server is made. The array of used GUIDs and highest backup USNs of a server formed in this way over time provides the history of backup and restoration of the server and is used to avoid replicating changes by the restored server that have already been replicated. Similarly, for the partition re-addition case, the array of used GUIDs and the new GUID assigned to a server after partition re-addition may be used to reliably and efficiently replicate old and new changes to other databases in the network.
Other features of the present invention are described below.